\section{Problema 1}

\subsection{Enunciado}

En la continuaci\'on de la pel\'icula Tiempo de Valientes el Licenciado Mariano Silverstein se encuentra al frente de la
brigada y debe detectar un grupo de agentes que siguen siendo fieles a Lebonian. Por lo tanto Mariano examina a los
agentes con un procedimiento simple y efectivo que determina qu\'e tan confiable, a la brigada, es un grupo de agentes. \\

Mariano determina la confiabilidad de un grupo de agentes utilizando una encuesta que mide la confianza entre los
mismos, los agentes deben opinar sobre cada uno, inclusive ellos mismos. Como resultado de la encuesta, Mariano obtiene
un conjunto de afirmaciones de la forma ``X dice que Y es confiable", ``X dice que Y no es confiable". Si X es confiable
entonces Mariano asume que lo que el agente opina siempre es verdadero. Caso contrario, si X no es confiable, entonces
las opiniones pueden ser verdaderas o falsas. Mariano quiere determinar la m\'axima cantidad de agentes en los que se
puede confiar, de modo que las respuestas a la encuesta sean consistentes. \\

Como ejemplo, asumamos que hay cuatro informantes A,B,C y D, que respondieron ``A dice que B es confiable pero
D no lo es", ``B dice C no es confiable", ``C dice que A y D son confiables''. En este caso hay a lo sumo dos informantes
de confianza. \\

Se debe escribir un programa que ayude a Mariano a determinar los agentes en que puede confiar. Es decir, que busque
el conjunto m\'as grande de agentes tal que:

\begin{itemize}
  \item Ning\'un agente en el conjunto diga que es confiable un agente que no esta en el conjunto.
  \item Ning\'un agente en el conjunto diga que no es confiable un agente en el conjunto.
\end{itemize}

La entrada consiste de varios casos que se deben procesar en lote. Cada caso comienza con dos enteros no negativos
$0 <= i$ y $0 <= a$, separados por espacios en blancos. $i$ es el n\'umero de informantes y $a$ es el n\'umero de respuestas a encuestas.
Luego hay $a$ l\'ineas, cada una con dos n\'umeros $x$ e $y$ ($1 <= x <= i$, $1 <= |y| <= i$) separados por espacios en blanco. Si $y$ es
positivo, la l\'inea de entrada significa que el agente ``$x$ dice que el agente $y$ es confiable''. Si y es negativo entonces, la l\'inea
de entrada significa que el agente ``$x$ dice que el agente $-y$ no es confiable''. El final de la entrada se indica con una l\'inea con dos ceros.
Por cada caso de entrada escribir en la salida una l\'nea con la m\'axima cantidad de agentes. \\

Analizar la complejidad temporal utilizando el modelo uniforme y expresarla en funci\'on de $i$ y de $a$. Encontrar un
algoritmo utilizando backtracking que tenga peor caso mejor que $O(2^{i} i^{3} a^{3})$. Evaluar diferentes podas y determinar casos
malos para cada una.

\subsection{Introducci\'on}

Sea S un conjunto de i agentes numerados desde 1 hasta  i,  y  E un conjunto de opiniones positivas o negativas.
Recorremos los subconjuntos de S, de forma sistemática. Descartamos aquellos subconjuntos que no son consistentes
con el problema (ningún agente confía en alguien que no está en el conjunto seleccionado ni desconfía de alguien que
sí lo está ). Entre los candidatos a solución, elegimos alguno de los que tienen máximo cardinal.

\subsection{Elección de la estructura} %FIXME: Tal vez esto no vaya, esta sección no está en ninguno de los demás problemas.

El TAD Conjunto (de agentes, en este caso) está implementado como un  vector de bits, de una cantidad acotada de tipos
distintos de elementos. La complejidad temporal de agregar o eliminar un elemento es del orden de O(1).

El TAD Encuesta está implementado como dos matrices de i x i. La complejidad temporal de determinar si un agente confía en otro,
o si desconfía de otro, es del orden de O(1).

\subsection{Correctitud}

Sean  S un conjunto de i agentes numerados desde 1 hasta  $i$,  y $P(S)$ = “conjunto partes de S”
Como i es una cantidad finita, también lo es la cantidad de subconjuntos de S  ( $|P| = 2i$ ).
La solución al problema es el cardinal de algún elemento de $P$ –-llamémosla v— cuyos agentes deben verificar ciertas propiedades entre sí. Si hay más de un conjunto que verifique dichas condiciones, será el mayor cardinal.

Proponemos el siguiente algoritmo:

\begin{algorithm}[H]
	\caption{solucion1(conjunto de agentes $S$, encuesta $E$)}
\begin{algorithmic}
	\STATE $v \leftarrow 0$
	\FOR{\textbf{cada} Agente $p$ \textbf{en} $P(S)$}
		\IF{$v\acute{a}lido?(p,E)$}
			\IF{$|p| > v$}
				\STATE  $v \leftarrow |p|$
			\ENDIF
		\ENDIF
	\ENDFOR
	\RETURN $v$
\end{algorithmic}
\end{algorithm}

$v\acute{a}lido?$ compara cada agente presente en $p$ con los restantes, y devuelve $true$ si se cumple el criterio anteriormente mencionado, según la encuesta $E$. \\

Soluciona correctamente el problema porque:
\begin{itemize}
	\item inspecciona una cantidad finita de casos (el algoritmo termina)
	\item la función $v\acute{a}lido?$ garantiza que el conjunto cumple con las propiedades pedidas, y lo hace también por inspección de una cantidad finita de elementos.
\end{itemize}

Definido de forma recursiva, un conjunto es: un conjunto vacío ó se construye agregando, ó no, un elemento a un conjunto.
Cambiamos el algoritmo para que se adapte a esta nueva definición de conjunto. Optamos por aplicar la técnica de backtracking,
para inspeccionar de forma organizada cada elemento de $P$ y aprovechar la recursividad.

\begin{algorithm}[H]
	\caption{recorrer(agente\_actual $i$, conjunto $p$, encuesta $E$)}
\begin{algorithmic}
	\STATE \textbf{global} $v$; //$v$ es una variable global incializada en $0$.
	\STATE
	\IF{$i = |S| + 1$}
		\IF{$v\acute{a}lido?(p,E)$}
			\IF{$|p| > v$}
				\STATE  $v \leftarrow |p|$
			\ENDIF
		\ENDIF
	\ELSE
		\STATE $recorrer(i+1, p, E)$
		\STATE $recorrer(i+1, p \cup \{i\}, E)$
	\ENDIF
\end{algorithmic} 
\end{algorithm}

$recorrer(i+1, p, E)$  examina los conjuntos que tienen los elementos actuales de $p$, a los que no pertenece $i$.
$recorrer(i+1, p \cup \{i\}, E)$, en cambio, los conjuntos que tienen los elementos actuales de $p$, y además a los que pertenece $i$.

Si la función es llamada con $i=0$, $p = \textrm{vacío}$, y una encuesta correcta según el enunciado, entonces cuando $i = |S|+1$
es que se ha llegado a un subconjunto de $S$. Y ya está en condiciones de evaluar como en el algoritmo anterior.
Los algoritmos, son equivalentes. Y por lo tanto, éste es correcto.

Pero, suponiendo que una determinada configuración no verificase el criterio, tan solo por la presencia de un agente, nos veríamos obligados
a inspeccionar conjuntos que lo contengan, aunque el resultado fuera el mismo.

Entonces, en lugar de hacer $|S|$ evaluaciones por cada uno de los $|S|$ agentes al finalizar la construcción del subconjunto, con $v\acute{a}lido?$,
realizamos $i$ evaluaciones en cada llamada recursiva, antes de agregar cada agente.

Las podas seguirán las siguientes reglas, para determinar si una rama es prometedora o no. Si no es ni prometedora ni no-prometedora
(léase, es prometedor no agregarlo), simplemente continuamos con el algoritmo de backtracking (es decir, intentar con ambas ramas):

\begin{itemize}
	\item $i \; \textrm{es prometedor} \Leftrightarrow \exists k < i, \textrm{tal que} \; k \in p \; \textrm{y} \; k \; \textrm{confía en} \; i$
	\item $i \; \textrm{es no prometedor} \Leftrightarrow P1(i) \vee P2(i) \vee P3(i) \vee P4(i)$
\end{itemize}

\noindent donde:

\begin{itemize}
	\item P1(i): $i$ desconfia de si mismo.
	\item P2(i): $\exists \; k \in p$, tal que $k$ no confía en $i$.
	\item P3(i): $\exists \; k \in p$ , tal que $i$ no confía en $k$.
	\item P4(i): $\exists \; k < i $, tal que $k \notin p$ e $i$ confía en $k$.
\end{itemize}

Versión con podas:

\begin{algorithm}[H]
	\caption{recorrer(agente\_actual $i$, conjunto $p$, encuesta $E$)}
\begin{algorithmic}
	\STATE \textbf{global} $v$; //$v$ es una variable global incializada en $0$.
	\STATE
	\IF{$i = |S| + 1$}
		\IF{$v\acute{a}lido?(p,E)$}
			\IF{$|p| > v$}
				\STATE  $v \leftarrow |p|$
			\ENDIF
		\ENDIF
	\ELSE
		\IF{$i$ es prometedor \textbf{y} no prometedor}
			\RETURN // Ninguna rama
			
		\ELSE
			\IF{$i$ es no prometedor}
				\STATE $recorrer(i+1, p, E)$ //descarto rama con $i$
			\ELSE
				\IF{$i$ es prometedor}
					\STATE $recorrer(i+1, p U {i}, E)$ //descarto rama sin $i$
				\ELSE
					\STATE $recorrer(i+1, p, E)$
					\STATE $recorrer(i+1, p \cup \{i\}, E)$ //pruebo ambas ramas
				\ENDIF
			\ENDIF
		\ENDIF
	\ENDIF
\end{algorithmic} 
\end{algorithm}

Las funciones booleanas que determinan si un agente confía o desconfía de otro, ó no, tienen complejidad temporal del orden de $O(1)$.
Al costo de una complejidad espacial del orden de $O(i^{2})$.

Las que determinan si son prometedores o no prometedoras, no evalúan al agente $i$ con los agentes $k$ de mayor numeración.
Siempre comparan con el anterior, asumiendo que se lo intentará agregar a un conjunto en donde aún no hay ningún conflicto.

La función $v\acute{a}lido?$ está especificada como: \\
$$v\acute{a}lido?(p,E) = \forall i \in p, ((\forall k \in S) (conf\acute{i}a(i, k, E) \Leftrightarrow k \in p )) \; \textrm{\textbf{y}} \; ((\forall k \in S) (desconf\acute{i}a(i, k, E) \Leftrightarrow k \notin p))$$


Para hacerlo más legible, desde ahora los nombraremos como lemas:\\
Lema1 (“Todos confían entre sí”)
	$$(\forall k \in S) (conf\acute{i}a(i, k, E) \Leftrightarrow k \in p )$$
Lema2 (“Sólo confían en ellos”)
	$$(\forall k \in S) (desconf\acute{i}a(i, k, E) \Leftrightarrow k \notin p)$$


Si $prometedor(i, p, E)$ es verdadero, entonces un subconjunto $p'$ de $S$ al que no pertenezca i no es un conjunto válido. Pues, según las condiciones alguien de $p'$ confiaba en él y no se cumple el Lema2  (“Sólo confían en ellos”)
Hay que agregarlo.\\
		$$prometedor(i, p, E) \Rightarrow  v\acute{a}lido?(p' , E)$$   
es falso.	   	\\
Pero si  $prometedor(i, p, E)$ es falso, no hay sustento lógico para descartarlo. Pero tampoco para aceptarlo. Queda una segunda evaluación.\\


Si $no-prometedor(i, p, E)$ es verdadero,  entonces  cualquier subconjunto $p''$ de $S$ al que pertenezca $i$  no es un conjunto válido porque, por cualquiera de las cuatro proposiciones antes mencionadas (P1, P2, P3, P4), no se cumpliría el Lema1 (“Todos confían entre sí”)\\
		$$no-prometedor(i, p, E) \Rightarrow  v\acute{a}lido?(p'' , E)$$
es falso.\\
Pero si  $no-prometedor(i, p, E)$ es falso, no hay sustento lógico para descartarlo.\\

Cuando $i=|S|+1$, no hay más agentes que evaluar y ya se construido un conjunto definitivo en el cual no se contradijo ninguna propiedad. Al final, fuerza la veracidad de $v\acute{a}lido?(p$\_$definitivo, E)$,  que es lo que buscábamos para considerarlo como una posible solución. Se obtiene el mismo resultado.
\\
Los algoritmos son equivalentes. Siguen inspeccionando una cantidad finita.
En conclusión, el problema resuelve correctamente el problema.


\subsection{Pseudoc\'odigo}

\begin{algorithm}[H]
\caption{prometedor(Agente $a$, Agentes $grupoActual$, Encuestas $encuestas$)}
\begin{algorithmic}
	\FOR{\textbf{cada} Agente $i$ \textbf{en} $grupoActual$}
		\IF{$confiaEn(i, a, encuestas)$}
			\RETURN \TRUE
		\ENDIF
	\ENDFOR
	\RETURN \FALSE
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{noPrometedor(Agente $a$, Agentes $agentes$, Agentes $grupoActual$, Encuestas $encuestas$)}
\begin{algorithmic}
	\IF{$desconfiaDe(a, a, encuestas)$}
		\RETURN \TRUE
	\ENDIF
	\STATE
	
	\FOR{Agente $i$ \textbf{desde} $1$ \textbf{hasta} $a$}
		\IF{$esta(i, grupoActual)$}
			\IF{$desconfiaDe(i, a, encuestas)$}
				\RETURN \TRUE
			\ENDIF
			\STATE
			
			\IF{$desconfiaDe(a, i, encuestas)$}
				\RETURN \TRUE
			\ENDIF
			\STATE
		
% 			\FOR{\textbf{cada} Agente $j$ \textbf{en} $agentes$}
% 				\IF{$confiaEn(a, j, encuestas)$ \textbf{y} $desconfiaDe(i, j, encuestas)$}
% 					\RETURN \TRUE
% 				\ENDIF
% 				\STATE
% 				
% 				\IF{$confiaEn(i, j, encuestas)$ \textbf{y} $desconfiaDe(a, j, encuestas)$}
% 					\RETURN \TRUE
% 				\ENDIF
% 			\ENDFOR
		\ELSE
			\IF{$confiaEn(i, a, encuestas)$}
				\RETURN \TRUE
			\ENDIF
		\STATE
		\ENDIF
	\ENDFOR
	
	\RETURN \FALSE
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{intentar(Agente $a$, Agentes $grupoActual$, Agentes $agentes$, Encuestas $encuestas$, Entero $\&max$)}
\begin{algorithmic}
	\IF{$a >= tama\tilde{n}o(agentes)$}
		\IF{$tama\tilde{n}o(grupoActual) > max$}
			\STATE $max \Leftarrow tama\tilde{n}o(grupoActual)$
		\ENDIF
		\STATE
		
		\RETURN
	\ENDIF
	\STATE
	
	\IF{$prometedor(a, grupoActual, encuestas)$ \textbf{y} $noPrometedor(a, agentes, grupoActual, encuestas)$}
		\RETURN
	
	\ELSE 
		\IF{$prometedor(a, grupoActual, encuestas)$}
			\STATE $agregar(a, grupoActual)$
			\STATE $intentar(a+1, grupoActual, agentes, encuestas, max)$
		
		\ELSE
			\IF{$noPrometedor(a, agentes, grupoActual, encuestas)$}
				\STATE $intentar(a+1, grupoActual, agentes, encuestas, max)$
			
			\ELSE
				\STATE $intentar(a+1, grupoActual, agentes, encuestas, max)$
				\STATE $agregar(a, grupoActual)$
				\STATE $intentar(a+1, grupoActual, agentes, encuestas, max)$
			\ENDIF
		\ENDIF
	\ENDIF
\end{algorithmic}
\end{algorithm}

\subsection{An\'alisis de Complejidad}

\subsubsection{Complejidad Prometedor}

En $prometedor$ tenemos un ciclo que recorre todos los elementos del grupo de agentes que se est\'a creando, y por cada agente
se pregunta si este es conf\'ia en el agente que se est\'a evaluando o no. As\'i que en total tenemos:

$$ \sum_{i=1}^{k} C $$

Donde $C$ es constante y $k = \sharp GrupoActual <= \sharp Agentes = n$, entonces:

$$ \sum_{i=1}^{k} C <=  \sum_{i=1}^{n} C = Cn \in O(n) $$

\subsubsection{Complejidad NoPrometedor}

En $noPrometedor$ tenemos un ciclo que recorre todos los elementos del grupo de agentes que se est\'a creando, y por cada agente
hace unos chequeos que se realizan en $O(1)$, entonces tenemos:

$$ \sum_{i=1}^{k}(C) + C' $$

Donde $C$, $C'$ y $C''$ son constantes y $k = \sharp GrupoActual <= \sharp Agentes = n$, entonces:

%$$ \sum_{i=1}^{k}(C + \sum_{j=1}^{n}C') + C'' <= \sum_{i=1}^{n}(C + \sum_{j=1}^{n}C') + C'' = \sum_{i=1}^{n}(C + C'n) + C'' = C'n^{2} + Cn + C'' \in O(n{2}) $$
$$ \sum_{i=1}^{k}(C) + C' <= \sum_{i=1}^{n}(C) + C' = Cn + C' \in O(n) $$

\subsubsection{Complejidad Intentar}

Ahora como paso final nos falta analizar la complejidad de $intentar$. En $intentar$ tenemos una llamada a $prometedor$, una llamada
a $noPrometedor$ y en el peor caso (en que el agente que se est\'a analizando no sea ni prometedor ni no prometedor) dos llamadas
recursivas. Por lo tanto nos queda:

$$
T(n) = \left\{
\begin{array}{cl}
1 &\mbox{si } n = 1\\
%C + C'n + C''n^{2} + T(n-1) + T(n-1) &\mbox{si } n > 1
T(n-1) + T(n-1) + Cn + C' &\mbox{si } n > 1
\end{array}\right.
$$

El caso base (cuando $n = 1$) es solamente un chequeo y una asignaci\'on as\'i que $\in O(1)$. Lo que interesa desarrollar es la parte recursiva
que se detalla a continuaci\'on:

%$$ T(n) = C + C'n + C''n^{2} + T(n-1) + T(n-1) $$
$$ T(n) = T(n-1) + T(n-1) + Cn + C' $$

Donde  $C$, y $C'$ son constantes tales que $C, C' <= K$, entonces:

$$ T(n) = T(n-1) + T(n-1) + Cn + C' = 2T(n-1) + Cn + C' <= 2T(n-1) + Kn + K = 2T(n-1) + K(n + 1) $$

Ahora vamos a desarrollar un poco $T(n)$ para ver que pinta tiene:

$$ T(n) <= 2T(n-1) + K(n + 1) = 2(2T(n-2) + K(n + 1)) + K(n + 1) = 2^{2}T(n-2) + 2K(n + 1) + K(n + 1) $$
$$ = 2^{2}(2T(n-3) + K(n + 1)) + 2K(n + 1) + K(n + 1)  = 2^{3}T(n-3) + 2^{2}K(n + 1) + 2K(n + 1) + K(n + 1) $$
$$ = 2^{3}T(n-3) + (2^{2} + 2^{1} + 2^{0})K(n + 1) $$

Si seguimos desarrollando la ecuaci\'on, en la iteraci\'on k vamos a tener:

$$ T_{k}(n) <= 2^{k}T(n-k) + \sum_{i=0}^{k-1}(2^{i})K(n + 1) $$

y en la iteraci\'on $n-1 esima$:

$$ T(n) <= 2^{n-1}T(1) +  \sum_{i=0}^{n-2}(2^{i})K(n + 1) = 2^{n-1} + 2^{n-2+1}K(n + 1) = 2^{n-1} + 2^{n-1}K(n + 1) $$
$$ 2\;2^{n-1}K(n + 1) = 2^{n}K(n + 1)$$

Por último,

$$ 2^{n}(n + 1) = 2^{n} n + 2^{n} <  2^{n} n + 2^{n} n = 2 (2^{n} n) $$

Por lo tanto, T(n) es del orden de $O(2^{n} n)$. \\

Haciendo un renombre de variables (pues $n$ es la cantidad de agentes, es decir, $i$), se concluye que la complejidad temporal
del algoritmo que resuelve el problema es del orden de $O(2^{i} i)$.

\subsection{Mediciones}

\subsubsection{Mejor Caso}

El mejor caso del algoritmo se presenta cuando a lo sumo se pasa una vez por cada agente. Esto se logra haciendo que cada
agente desconfíe de si mismo y por lo tanto siempre se tome la rama en la que no se lo agrega a la solución final. En ese caso
la complejidad del algoritmo $\in O(i^{2})$ ya que se tienen que recorrer los $i$ agentes y por cada agente evaluar las podas
que a lo sumo tardan $O(i)$.

\includegraphics[width=\textwidth]{problema1/mejor.png}

\subsubsection{Peor Caso}

El peor caso se presenta cuando ningún agente opina sobre otro agente en el grupo o sobre si mismo. En este caso en cada nivel
del árbol de decisión se tienen que recorrer sí o sí las dos ramas ya que cualquiera de las dos puede formar parte de la 
solución final. Por lo tanto la complejidad en este caso sería $O(2^{i}i)$. 

\includegraphics[width=\textwidth]{problema1/peor.png}

\subsubsection{Casos aleatorios}
Para los casos aleatorios se crearon instancias que iban creciendo en tamaño, donde la cantidad de encuestas y las opiniones de los agentes se determinaban de forma aleatoria. En el gráfico se aprecia como la cota en el peor caso del algoritmo es dificilmente alcanzada debido a las diferentes podas que se realizan.

\includegraphics[width=\textwidth]{problema1/aleatorio.png}

\subsubsection{Comparación de los distintos casos}

En el siguiente gráfico se comparan los mejores casos con los casos aleatorios.

\includegraphics[width=\textwidth]{problema1/mejor-aleatorio.png}

En este otro se comparan los 3 casos de prueba.

\includegraphics[width=\textwidth]{problema1/mejor-aleatorio-peor.png}

\newpage
